#include"PriQueue.h"

template<typename T>
PriQueue<T>::PriQueue(T* arr, int len)
{
	maxsize = len>maxsize ? len : maxsize;
	data = new T[maxsize];
	cursize = len;
	for (int i = 0; i<len; ++i)
	{
		data[i] = arr[i];
	}
	MakeHeap();
}

template<typename T>
void PriQueue<T>::Pop()
{
	data[0] = data[cursize - 1];
	--cursize;
	FilterDown(0, cursize - 1);
}

template<typename T>
void PriQueue<T>::Push(const T& x)
{
	if (cursize >= maxsize) return;
	data[cursize] = x;
	FilterUp(cursize);
	++cursize;
}

template<typename T>
void PriQueue<T>::FilterDown(int begin, int end)
{
	int parent = begin;
	int son = 2 * parent + 1;
	T tmp = data[parent];
	while (son <= end)
	{
		//如果右子树没有节点则不比较
		if (son + 1 < end)
			son = data[son]<data[son + 1] ? son : son + 1;

		if (tmp <= data[son]) break;
		data[parent] = data[son];
		parent = son;
		son = parent * 2 + 1;
	}
	data[parent] = tmp;
}

template<typename T>
void PriQueue<T>::FilterUp(int index)
{
	int son = index;
	int parent = (son - 1) / 2;
	T tmp = data[index];
	while (son > 0)
	{
		if (tmp > data[parent]) break;
		data[son] = data[parent];
		son = parent;
		parent = (son - 1) / 2;
	}
	data[son] = tmp;
}

template<typename T>
void PriQueue<T>::MakeHeap()
{
	int end = cursize - 1;
	int lastroot = (end - 1) / 2;
	while (lastroot >= 0)
	{
		FilterDown(lastroot, end);
		--lastroot;
	}
}